# LeetCode 785、判断二分图
# 一、题目描述
存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
- 不存在自环（
graph[u]不包含u）。 - 不存在平行边（
graph[u]不包含重复值）。 - 如果
v在graph[u]内，那么u也应该在graph[v]内（该图是无向图） - 这个图可能不是连通图，也就是说两个节点
u和v之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
如果图是二分图，返回 true ；否则，返回 false 。
示例 1：
img
输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。
示例 2：
img
输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。
提示：
graph.length == n1 <= n <= 1000 <= graph[u].length < n0 <= graph[u][i] <= n - 1graph[u]不会包含ugraph[u]的所有值 互不相同- 如果
graph[u]包含v，那么graph[v]也会包含u
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：278166530
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 深度优先遍历的解法
class Solution {
public boolean isBipartite(int[][] graph) {
// 每个节点都有一个介于 0 到 n - 1 之间的唯一编号
// 定义 visited 数组，记录访问每个节点时应该设置为什么颜色
// 每个索引的元素值代表当前索引（节点）的访问情况
// 初始值为 0 表示未被访问
// 被访问的时候根据情况赋值为 1 或者 -1
// 根据动画演示
// 1 表示黄色
// -1 表示绿色
int[] visited = new int[graph.length];
// 采取深度优先遍历的方式对 graph 里面的每个节点进行访问
for (int i = 0; i < graph.length; i++) {
// 只有当前这个节点处于未被渲染的状态，才有资格对它进行处理
if (visited[i] == 0) {
// 在访问过程中，如果出现了去设置某个节点的颜色时产生了冲突，那么就直接返回结果
// 比如 5 这个节点之前被渲染为黄色
// 再处理其它节点的时候，重新渲染 5，需要把它渲染为绿色
// 此时，产生了矛盾，表示无法分割成独立的子集
if(dfs(graph, i, 1, visited) == false){
return false;
}
}
}
return true;
}
// 图深度优先遍历
// 返回值：是否会出现矛盾的节点
// graph：二维矩阵
// v：节点值，同时也是数组 visited 里面的索引值
// color：设置的颜色 1 表示黄色 -1 表示绿色
// visited：记录访问每个节点时应该设置为什么颜色
private boolean dfs(int[][] graph, int v, int color, int[] visited) {
// 如果当前 v 这个节点已经被染色了
if (visited[v] != 0) {
// 判断它的颜色是否与本次要染的颜色相同
if( visited[v] == color){
// 如果相同，说明此无向图可以被正确染色
return true;
}else{
// 如果矛盾，说明此无向图无法被正确染色
return false;
}
}
// 否则，说明当前 v 这个节点还没有被染色
// 对当前顶点进行染色，设置为 color
visited[v] = color;
// 再对和它相邻的所有节点都设置为与 color 相反的颜色
for (int w: graph[v]) {
// 每个相邻的节点都使用 dfs 进行渲染为 -color 的颜色
// 在渲染过程中，记录是否可以正确染色
boolean res = dfs(graph, w, -color, visited);
// 如果发现无法正确染色
if(res == false){
// 返回 false
return false;
}
}
// 否则说明以当前 v 这个节点进行深度优先遍历的方式访问的所有节点
// 均没有出现矛盾的现象
// 可以返回 true
return true;
}
}
# Java
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：278166530
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 广度优先遍历的解法
class Solution {
public boolean isBipartite(int[][] graph) {
// 每个节点都有一个介于 0 到 n - 1 之间的唯一编号
// 定义 visited 数组，记录访问每个节点时应该设置为什么颜色
// 每个索引的元素值代表当前索引（节点）的访问情况
// 初始值为 0 表示未被访问
// 被访问的时候根据情况赋值为 1 或者 -1
// 根据动画演示
// 1 表示黄色
// -1 表示黄色
int[] visited = new int[graph.length];
// 借助队列实现广度优先遍历
Queue<Integer> queue = new LinkedList<>(); //广度搜索队列
// 采取广度优先遍历的方式对 graph 里面的每个节点进行访问
// 一层一层访问
for (int i = 0; i < graph.length; i++) {
// 只有当前这个节点处于未被渲染的状态，才有资格对它进行处理
// 如果当前这个节点已经被渲染了，那么去查看其它的节点
if (visited[i] != 0) {
continue;
}
// 否则，把当前节点加入到队列里面
queue.offer(i);
// 同时设置当前节点的颜色
// 为什么这里设置为 1 ，为黄色呢？
// 如果发现当前这个节点还不是某个节点的相邻节点，就设置为黄色
visited[i] = 1;
// 广度优先遍历
while (!queue.isEmpty()) {
// 取出队头元素
int v = queue.poll();
// graph[v]存放的是与节点 v 相连的所有节点
// 访问这些节点
for (int w: graph[v]) {
// 如果当前节点的某个邻接点已经被染过色了
// 且颜色和当前顶点相同，产生了矛盾，说明此无向图无法被正确染色
if (visited[w] == visited[v]) {
// 返回 false
// 无需继续访问其它节点了
return false;
}
// 如果当前节点的某个邻接点没有被染过色了
if (visited[w] == 0) {
// 把它设置为何当前节点相反的颜色
visited[w] = -visited[v];
// 同时把它也加入到队列当中
queue.offer(w);
}
}
}
}
return true;
}
}
# **2、**C++ 代码
# 3、Python 代码
登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com
# 作者：程序员吴师兄
# 微信：278166530
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 广度优先遍历的解法
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
# 每个节点都有一个介于 0 到 n - 1 之间的唯一编号
# 定义 visited 数组，记录访问每个节点时应该设置为什么颜色
# 每个索引的元素值代表当前索引（节点）的访问情况
# 初始值为 0 表示未被访问
# 被访问的时候根据情况赋值为 1 或者 -1
# 根据动画演示
# 1 表示黄色
# -1 表示黄色
n = len(graph)
visited = [0] * n
# 借助队列实现广度优先遍历
queue = collections.deque()
# 采取广度优先遍历的方式对 graph 里面的每个节点进行访问
# 一层一层访问
for i in range(n):
# 只有当前这个节点处于未被渲染的状态，才有资格对它进行处理
# 如果当前这个节点已经被渲染了，那么去查看其它的节点
if visited[i] != 0 :
continue
# 否则，把当前节点加入到队列里面
queue.append(i)
# 同时设置当前节点的颜色
# 为什么这里设置为 1 ，为黄色呢？
# 如果发现当前这个节点还不是某个节点的相邻节点，就设置为黄色
visited[i] = 1
# 广度优先遍历
while queue:
# 取出队头元素
v = queue.popleft()
# graph[v]存放的是与节点 v 相连的所有节点
# 访问这些节点
for w in graph[v]:
# 如果当前节点的某个邻接点已经被染过色了
# 且颜色和当前顶点相同，产生了矛盾，说明此无向图无法被正确染色
if visited[w] == visited[v] :
# 返回 false
# 无需继续访问其它节点了
return False
# 如果当前节点的某个邻接点没有被染过色了
if visited[w] == 0 :
# 把它设置为何当前节点相反的颜色
visited[w] = -visited[v]
# 同时把它也加入到队列当中
queue.append(w)
return True
登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 微信：278166530
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 深度优先遍历的解法
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
# 每个节点都有一个介于 0 到 n - 1 之间的唯一编号
# 定义 visited 数组，记录访问每个节点时应该设置为什么颜色
# 每个索引的元素值代表当前索引（节点）的访问情况
# 初始值为 0 表示未被访问
# 被访问的时候根据情况赋值为 1 或者 -1
# 根据动画演示
# 1 表示黄色
# -1 表示绿色
n = len(graph)
visited = [0] * n
# 采取深度优先遍历的方式对 graph 里面的每个节点进行访问
for i in range(n):
# 只有当前这个节点处于未被渲染的状态，才有资格对它进行处理
if visited[i] == 0 :
# 在访问过程中，如果出现了去设置某个节点的颜色时产生了冲突，那么就直接返回结果
# 比如 5 这个节点之前被渲染为黄色
# 再处理其它节点的时候，重新渲染 5，需要把它渲染为绿色
# 此时，产生了矛盾，表示无法分割成独立的子集
if self.dfs(graph, i, 1, visited) == False :
return False
return True
# 图深度优先遍历
# 返回值：是否会出现矛盾的节点
# graph：二维矩阵
# v：节点值，同时也是数组 visited 里面的索引值
# color：设置的颜色 1 表示黄色 -1 表示绿色
# visited：记录访问每个节点时应该设置为什么颜色
def dfs(self,graph, v, color,visited) -> bool:
# 如果当前 v 这个节点已经被染色了
if visited[v] != 0 :
# 判断它的颜色是否与本次要染的颜色相同
if visited[v] == color:
# 如果相同，说明此无向图可以被正确染色
return True
else:
# 如果矛盾，说明此无向图无法被正确染色
return False
# 否则，说明当前 v 这个节点还没有被染色
# 对当前顶点进行染色，设置为 color
visited[v] = color
# 再对和它相邻的所有节点都设置为与 color 相反的颜色
for w in graph[v]:
# 每个相邻的节点都使用 dfs 进行渲染为 -color 的颜色
# 在渲染过程中，记录是否可以正确染色
res = self.dfs(graph, w, -color, visited)
# 如果发现无法正确染色
if res == False :
# 返回 false
return False
# 否则说明以当前 v 这个节点进行深度优先遍历的方式访问的所有节点
# 均没有出现矛盾的现象
# 可以返回 true
return True